class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    /*
    基于红黑树的multiset辅助算法：查询时间复杂度O(nlogn)，插入时间复杂度O(logn)
	(时间复杂度过高)
    */
    multiset<int, less<int>> numSet;

    void addNum(int num) {
        //按从大到小的顺序插入numSet中
        numSet.insert(num);
    }
    
    double findMedian() {
        multiset<int, less<int>>::iterator it = numSet.begin();
        int length = numSet.size();
        if(length == 0)  return 0.0;
        double medium = 0;
        if(length & 1){
            for(int i = 0; i < length/2; ++i)  ++it;
            medium = *it;
        }else{
            for(int i = 0; i < (length/2 - 1); ++i)  ++it;
            medium = ((double)*it + (double)*(++it)) / 2.0;
        }
        return medium;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
 
 /*********************************************************************************/
 class MedianFinder {
private:
    vector<int> min;
    vector<int> max;
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    /*
    基于STL的push_heap、pop_heap及vector实现最大堆最小堆：(使用比较仿函数less<T>(), greater<T>())
    查询时间复杂度O(1)，插入时间复杂度O(logn)
    需要保证：最大堆中的元素均小于最小堆中的元素；最大堆与最小堆数目之差不能超过1，
    为此可选择在总数目为偶数时将新元素插入最小堆中。
    push_heap()是向堆中插入一个元素，并且使堆的规则依然成立;
    pop_heap()是在堆的基础上，弹出堆顶元素。
    */
    //堆模拟

    void addNum(int num) {
        //注意&运算符优先级比==低，需要使用括号
        if(((max.size() + min.size()) & 1) == 0){
            //若总数目之和是偶数,应该放最小堆
            if(max.size() > 0 && num < max[0]){
                //若需要插入的元素小于最小堆中的堆顶
                max.push_back(num);
                push_heap(max.begin(), max.end(), less<int>());

                num = max[0];

                pop_heap(max.begin(), max.end(), less<int>());
                max.pop_back();
            }

            min.push_back(num);
            push_heap(min.begin(), min.end(), greater<int>());
        }else{
            //总数之和是奇数，应放入最大堆
            if(min.size() > 0 && num > min[0]){
                min.push_back(num);
                push_heap(min.begin(), min.end(), greater<int>());

                num = min[0];

                pop_heap(min.begin(), min.end(), greater<int>());
                min.pop_back();
            }

            max.push_back(num);
            push_heap(max.begin(), max.end(), less<int>());
        }
    }
    
    double findMedian() {
        int sizePlus = max.size() + min.size();
        if(sizePlus == 0)  return 0.0;
        double medium = 0.0;
        if(sizePlus & 1){
            medium = min[0];    
        }else{
            medium = ((double)min[0] + (double)max[0]) / 2.0;
        }
        return medium;
    }
};